package 复习.博客2.递归和回溯;

import java.util.ArrayList;

public class 括号生成 {
    ArrayList<String> lists = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        backStacking("",n,0,0);
        return lists;
    }

    public void backStacking(String s,int n,int left,int right){
        if(s.length() == n * 2){
            lists.add(s);
        }

        if(left < n){
            backStacking(s + "(",n,left + 1,right);
        }
        if(left > right){
            backStacking(s + ")",n,left,right +1);
        }
    }
}


/*
ArrayList<String> list = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        backstacking("",0,0,n);
        return list;
    }

    public void backstacking(String s,int left,int right,int n){
        if(s.length() == n * 2){
            list.add(s);
            return;
        }

        if(left < n){
            backstacking(s + "(",left + 1,right,n);
        }
        if(left > right){
            backstacking(s + ")",left,right + 1,n);
        }
    }
 */